#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include <stddef.h>
#include <iostream>
// #include <MyInclude/LinkQueue.h>

template <typename T>
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    void Insert(const T &element);
    void Remove(const T &element);
    T *Find(const T &element);

    template <typename U>
    friend std::ostream &operator<<(std::ostream &os, BinaryTree<U> &tree);

private:
    struct TreeNode
    {
        TreeNode(const T &element) : data(element)
        {
            left = right = parent = nullptr;
        }
        T data;
        TreeNode *left;
        TreeNode *right;
        TreeNode *parent;
    };
    TreeNode *root;
    TreeNode *InsertNode(TreeNode *node, const T &element);
    TreeNode *RemoveNode(TreeNode *node, const T &element);
    T *FindNode(TreeNode *node, const T &element);
    TreeNode *GetMinNode(TreeNode *node);
    void PrevTravel(TreeNode *node) ;
    void MidTravel(TreeNode *node) ;
    void PostTravel(TreeNode *node) ;
    TreeNode *RotateRight(TreeNode *root);
    TreeNode *RotateLeft(TreeNode *root);
    TreeNode *RotateLeftRight(TreeNode *root);
    TreeNode *RotateRightLeft(TreeNode *root);
    int GetNodeHight(TreeNode *node);
    int LRDevition(TreeNode *node);
    void Free(TreeNode *node);
};

template <typename T>
BinaryTree<T>::BinaryTree()
{
    root = nullptr;
}

template <typename T>
BinaryTree<T>::~BinaryTree()
{
    Free(root);
}

template <typename T>
void BinaryTree<T>::Insert(const T &element)
{
    root = InsertNode(root, element);
}

template <typename T>
void BinaryTree<T>::Remove(const T &element)
{
    root = RemoveNode(root, element);
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::InsertNode(TreeNode *node, const T &element)
{
    if (node == nullptr)
    {
        return new TreeNode(element); //
    }
    if (node->data == element) // 二叉树不能存在重复元素 不插入重复元素
    {
        return node;
    }
    else if (node->data > element) // 当前结点比要插入是数大
    {
        node->left = InsertNode(node->left, element); // 递归到左子树
        // 左边重
        if (LRDevition(node) > 1)
        {
            // 左左
            if (node->left->data > element)
            {
                // 右旋
                node = RotateRight(node);
            }
            else
            // 左右失衡
            {
                // 左右旋
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right, element); // 递归到右子树
        // 右边重
        if (LRDevition(node) < -1)
        {
            // 右右
            if (node->right->data < element)
            {
                node = RotateLeft(node);
            }
            else
            // 右左
            {
                node = RotateRightLeft(node);
            }
        }
    }
    return node;
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RemoveNode(TreeNode *node, const T &element)
{
    if (node == nullptr) // 当前结点为空
        return nullptr;
    if (node->data < element) // 从根开始找 ，要删的大，向右找
    {
        node->right = RemoveNode(node->right, element);
    }
    else if (node->data > element) // 要删的小，往左找
    {
        node->left = RemoveNode(node->left, element);
    }
    else // 相等，开始删，分三种情况
    {
        // 叶子
        if (node->left == nullptr && node->right == nullptr) // 没有子树，直接删
        {
            delete node;
            return nullptr;
        }
        else if (node->left && node->right) // 左右子树都存在
        {
            // 取右子树中最小结点
            TreeNode *minNode = GetMinNode(node->right);
            node->data = minNode->data;
            node->right = RemoveNode(node->right, minNode->data);
        }
        // 有一个孩子
        else // 存在一个子树
        {
            TreeNode *child = node->left ? node->left : node->right;
            delete node;
            return child;
        }
    }
    // 左边重
    if (LRDevition(node) > 1)
    {
        // 左左
        if (LRDevition(node->left) > 0)
        {
            // 右旋
            node = RotateRight(node);
        }
        else
        // 左右失衡
        {
            // 左右旋
            node = RotateLeftRight(node);
        }
    }
    if (LRDevition(node) < -1)
    {
        // 右右
        if (LRDevition(node->right) < 0)
        {
            node = RotateLeft(node);
        }
        else
        // 右左
        {
            node = RotateRightLeft(node);
        }
    }
    return node;
}

template <typename T>
T *BinaryTree<T>::Find(const T &element)
{
    return FindNode(root, element);
}

template <typename T>
T *BinaryTree<T>::FindNode(TreeNode *node, const T &element)
{
    if (node == nullptr)
        return nullptr;
    if (node->data == element)
        return &node->data;
    else if (node->data > element)
        return FindNode(node->left, element);
    else
        return FindNode(node->right, element);
}

template <typename T>
void BinaryTree<T>::Free(TreeNode *node)
{
    if (node == nullptr)
    {
        return;
    }
    Free(node->left);
    Free(node->right);
    delete node;
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::GetMinNode(typename BinaryTree<T>::TreeNode *node)
{
    TreeNode *minNode = node;
    while (minNode->left)
        minNode = minNode->left;
    return minNode;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, BinaryTree<T> &tree)
{
    std::cout << "前序遍历:";
    tree.PrevTravel(tree.root);
    std::cout << std::endl;

    std::cout << "中序遍历:";
    tree.MidTravel(tree.root);
    std::cout << std::endl;

    std::cout << "后序遍历:";
    tree.PostTravel(tree.root);
    std::cout << std::endl;

    // std::cout << "层序遍历:";
    // LinkQueue q;
    // q.Push(tree.root);
    // while (!q.IsEmpty())
    // {
    //     typename BinaryTree<T>::TreeNode *node = (typename BinaryTree<T>::TreeNode *)*q.GetFront();
    //     q.Pop();
    //     std::cout << node->data << " ";
    //     if (node->left)
    //         q.Push(node->left);
    //     if (node->right)
    //         q.Push(node->right);
    // }
    // std::cout << std::endl;
    return os;
}

template <typename T>
void BinaryTree<T>::PrevTravel(typename BinaryTree<T>::TreeNode *node) 
{
    if (node == nullptr)
        return;
    std::cout << node->data << " ";
    PrevTravel(node->left);
    PrevTravel(node->right);
}

template <typename T>
void BinaryTree<T>::MidTravel(typename BinaryTree<T>::TreeNode *node) 
{
    if (node == nullptr)
        return;
    MidTravel(node->left);
    std::cout << node->data << " ";
    MidTravel(node->right);
}

template <typename T>
void BinaryTree<T>::PostTravel(typename BinaryTree<T>::TreeNode *node) 
{
    if (node == nullptr)
        return;
    PostTravel(node->left);
    PostTravel(node->right);
    std::cout << node->data << " ";
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateRight(TreeNode *root) // 右旋
{
    TreeNode *t = root->left; // 把这个值保存下来
    root->left = t->right;
    t->right = root;
    return t; // 返回新的根
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateLeft(TreeNode *root) // 左旋
{
    TreeNode *t = root->right;
    root->right = t->left;
    t->left = root;
    return t; // 返回新的结点
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateLeftRight(TreeNode *root) // 左右旋
{
    // 左子树左旋
    root->left = RotateLeft(root->left);
    return RotateRight(root); // 整棵树右旋
}

template <typename T>
typename BinaryTree<T>::TreeNode *BinaryTree<T>::RotateRightLeft(TreeNode *root) //
{
    // 右子树右旋
    root->right = RotateLeft(root->right);
    return RotateLeft(root); // 整棵树左旋
}

template <typename T>
int BinaryTree<T>::GetNodeHight(TreeNode *node)
{
    if (node == nullptr)
        return 0;
    int leftHight = GetNodeHight(node->left);
    int rightHight = GetNodeHight(node->right);
    return (leftHight > rightHight ? leftHight : rightHight) + 1;
}

template <typename T>
int BinaryTree<T>::LRDevition(TreeNode *node) // 左右是否平衡
{
    if (node == nullptr)
        return 0;
    return GetNodeHight(node->left) - GetNodeHight(node->right);
}

#endif